// https://www.lintcode.com/problem/add-two-numbers/

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param l1: the first list
     * @param l2: the second list
     * @return: the sum list of l1 and l2 
     */
    public ListNode addLists(ListNode l1, ListNode l2) {
        // write your code here
        ListNode head = null, tail = null;
        int step = 0; // 进位标记
        while ((l1 != null) && (l2 != null)) {
            ListNode node = new ListNode(l1.val + l2.val + step);
            if (node.val >= 10) {
                step = 1;
                node.val %= 10;
            }
            else {
                step = 0;
            }
            if (null == head) {
                head = node;
            }
            else {
                tail.next = node;
            }
            tail = node;
            l1 = l1.next;
            l2 = l2.next;
        }
        ListNode l3 = (null == l1) ? l2 : l1;
        while (l3 != null) {
            ListNode node = new ListNode(l3.val + step);
            if (node.val >= 10) {
                step = 1;
                node.val %= 10;
            }
            else {
                step = 0;
            }
            if (null == head) {
                head = node;
            }
            else {
                tail.next = node;
            }
            tail = node;
            l3 = l3.next;
        }
        if (step > 0) {
            tail.next = new ListNode(step);
        }
        return head;
    }
}